package com.sicheng.lc.杂题.LCA;

import java.util.ArrayDeque;
import java.util.List;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/8/21 10:08
 */
public class 树上倍增法 {
    // 和rmq算法很像 在蓝桥目录应该收录了rmq
    // 理论参考 里面也包含了2种暴力法 树上倍增的复杂度整体是NlogN 很适用一个用例n组数据测试
    // https://www.bilibili.com/read/cv13619734
    // 最近公共祖先问题----也可以求解任意2个点的距离
    static int N = (int) 1e5;
    List<Integer>[] g = new List[N + 1];
    static int[] d = new int[N + 1];
    static int K = (int) (Math.log(N) / Math.log(2));
    // f[i,j] 存i结点的2^j的祖先结点
    static int[][] f = new int[N + 1][K + 1];

    int k;

    // 这一步网上大部分是dfs构造的 但是我bfs的板子敲得次数太多就习惯bfs辽
    // 1.先读入数据构图 不是重点就不写辽 假设数据已经在里面了
    // 2.从根节点出发 初始化每层结点的深度 和每个结点的2^0父亲
    void bfs(int u) {
        ArrayDeque<Integer> q = new ArrayDeque<>();
        int step = 0;
        q.offer(u);
        // 根节点没有父亲给一个特殊值也可以把自己设置为自己的祖先没有问题
        f[u][0] = u;
        d[u] = 1;
        while (!q.isEmpty()) {
            step++;
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int x = q.poll();
                for (int y : g[x]) {
                    d[y] = step + 1;
                    f[y][0] = x;
                }
            }
        }
    }

    //3.初始化f[i,j] i的2^j父亲
    void init(int n) {
        k = (int) (Math.log(n) / Math.log(2));
        for (int j = 1; 1 << j <= n; j++) {
            for (int i = 1; i <= n; i++) {
                f[i][j] = f[f[i][j - 1]][j - 1];
            }
        }
    }

    //4.寻找x,y 的最近公共祖先
    //    4.1 y向上走到与x同层
    //    4.2 (x,y) 一起去向上走
    //    向上时统一技巧 从2^k 开始，减小偏移k 直到k降到0
    int lca(int x, int y) {
        //保证x的深度小于或等于y
        if (d[x] > d[y]) {
            //swap的位运算技巧懒得开一个临时变量temp
            x = x ^ y;
            y = x ^ y;
            x = x ^ y;
        }
        for (int i = k; i >= 0; i--)//y向上走到与x同一深度
            if (d[f[y][i]] >= d[x])
                y = f[y][i];
        if (x == y)
            return x;
        for (int i = k; i >= 0; i--)//x、y一起向上走
            if (f[x][i] != f[y][i]) {
                x = f[x][i];
                y = f[y][i];
            }
        return f[x][0];//返回x的父节点
    }


}
